如今，协同过滤推荐 (CollaboratIve Filtering) 技术已广泛应用于各类推荐系统中，其通常分为两类，一种是基于用户的协同过滤算法(User-Based CF)，它是根据用户对物品的历史评价数据(如，喜欢、点击、购买等)，计算不同用户之间的相似度，在有相同喜好的用户间进行物品推荐，例如将跟我有相同电影爱好的人看过的电影推荐给我；另一种是基于物品的协同过滤算法(Item-Based CF)，它是根据用户对物品的历史评价数据，计算物品之间的相似度，用户如果喜欢 A 物品，那么可以给用户推荐跟 A 物品相似的其他物品，例如如果我们在购物网站上买过尿片，第二天你再到购物网站上浏览时，可能会被推荐奶瓶。更多关于 User-Based CF 和 Item-Based CF 的阐述请参考文章。然而，在用户数量以及用户评分不足的情况下，上述两种方法就不是那么地好使了，近年来，基于模型的推荐算法 ALS(交替最小二乘) 在 Netflix 成功应用并取得显著效果提升，ALS 使用机器学习算法建立用户和物品间的相互作用模型，进而去预测新项。
基本原理
用户对物品的打分行为可以表示成一个打分矩阵 RRR，例如下表所示：
矩阵中的打分值 rijrijr_{ij} 表示用户 uiuiu_i 对物品 vjvjv_j 的打分，其中”?” 表示用户没有打分，这也就是要通过机器学习的方法去预测这个打分值，从而达到推荐的目的。
模型抽象
按照 User-Based CF 的思想，RRR 的行向量对应每个用户 uuu ，按照 Item-Based CF 的思想，RRR 的列向量对应每个物品 vvv 。ALS 的核心思想是，将用户和物品都投影到 kkk 维空间，也就是说，假设有 kkk 个隐含特征，至于 kkk 个隐含特征具体指什么不用关心，将每个用户和物品都用 kkk 维向量来表示，把它们之间的内积近似为打分值，这样就可以得到如下近似关系：
R≈UVTR≈UVT R \approx U V^T
RRR 为打分矩阵 (m×nm×nm \times n)，mmm 个用户，nnn 个物品，UUU 为用户对隐含特征的偏好矩阵 (m×km×km \times k)，VVV 为物品对隐含特征的偏好矩阵 (n×kn×kn \times k)。
上述模型的参数就是矩阵 UUU 和 VVV，即求解出 UUU 和 VVV 我们就可以重现打分矩阵，填补原始打分矩阵中的缺失值”?”。
显示反馈代价函数
要求解上述模型中的 UUU 和 VVV，那么就需要一个代价函数来衡量参数的拟合程度，如果有比较明确的显式反馈打分数据，那么可以比较重构出来的打分矩阵与实际打分矩阵，即得到重构误差，由于实际打分矩阵有很多缺失值，所以仅计算已知打分的重构误差，下面函数为显示反馈代价函数。
J(U,V)=∑i∑j[(rij−uivTj)2+λ(‖ui‖2+‖vj‖2)]J(U,V)=∑i∑j[(rij−uivjT)2+λ(‖ui‖2+‖vj‖2)] J\left( U, V \right) = \sumi \sum_j \left[ \left( r{ij} - u_i v_j^T \right)^2 + \lambda \left( |u_i|^2 + |v_j|^2 \right) \right]
rijrijr_{ij} 为矩阵 RRR 的第 iii 行第 jjj 列，表示用户 uiuiu_i 对物品 vjvjv_j 的打分，uiuiu_i 为矩阵 UUU 的第 iii 行 (1×k)(1×k)(1 \times k)，vTjvjTv_j^T 为矩阵 VTVTV^T 的第 jjj 列 (k×1)(k×1)(k \times 1)，λλ\lambda 为正则项系数。
隐式反馈代价函数
很多情况下，用户并没有明确反馈对物品的偏好，需要通过用户的相关行为来推测其对物品的偏好，例如，在视频推荐问题中，可能由于用户就懒得对其所看的视频进行反馈，通常是收集一些用户的行为数据，得到其对视频的偏好，例如观看时长等。通过这种方式得到的偏好值称之为隐式反馈值，即矩阵 RRR 为隐式反馈矩阵，引入变量 pijpijp_{ij} 表示用户 uiuiu_i 对物品 vjvjv_j 的置信度，如果隐式反馈值大于 0，置信度为 1，否则置信度为 0。
pij={1rij>00rij=0pij={1rij>00rij=0 p{ij} = \left{\begin{matrix}1 \qquad r{ij} > 0 & \ 0 \qquad r_{ij} = 0 & \end{matrix}\right.
但是隐式反馈值为 0 并不能说明用户就完全不喜欢，用户对一个物品没有得到一个正的偏好可能源于多方面的原因，例如，用户可能不知道该物品的存在，另外，用户购买一个物品也并不一定是用户喜欢它，所以需要一个信任等级来显示用户偏爱某个物品，一般情况下，rijrijr{ij} 越大，越能暗示用户喜欢某个物品，因此，引入变量 cijcijc{ij}，来衡量 pijpijp_{ij} 的信任度。
cij=1+αrijcij=1+αrij c{ij} = 1 + \alpha r{ij}
αα\alpha 为置信度系数
那么，代价函数则变成如下形式：
J(U,V)=∑i∑j[cij(pij−uivTj)2+λ(‖ui‖2+‖vj‖2)]J(U,V)=∑i∑j[cij(pij−uivjT)2+λ(‖ui‖2+‖vj‖2)] J\left( U, V \right) = \sumi \sum_j \left[ c{ij} \left( p_{ij} - u_i v_j^T \right)^2 + \lambda \left( |u_i|^2 + |v_j|^2 \right)\right]
算法
无论是显示反馈代价函数还是隐式反馈代价函数，它们都不是凸的，变量互相耦合在一起，常规的梯度下降法可不好使了。但是如果先固定 UUU 求解 VVV，再固定 VVV 求解 UUU ，如此迭代下去，问题就可以得到解决了。
U(0)→V(1)→U(1)→V(2)→⋯U(0)→V(1)→U(1)→V(2)→⋯ U^{(0)} \rightarrow V^{(1)} \rightarrow U^{(1)} \rightarrow V^{(2)} \rightarrow \cdots
那么固定一个变量求解另一个变量如何实现呢，梯度下降？虽然可以用梯度下降，但是需要迭代，计算起来相对较慢，试想想，固定 UUU 求解 VVV，或者固定 VVV 求解 UUU，其实是一个最小二乘问题，由于一般隐含特征个数 kkk 取值不会特别大，可以将最小二乘转化为正规方程一次性求解，而不用像梯度下降一样需要迭代。如此交替地解最小二乘问题，所以得名交替最小二乘法 ALS，下面是基于显示反馈和隐式反馈的最小二乘正规方程。
显示反馈
固定 VVV 求解 UUU
UT=(VTV+λI)−1VTRTUT=(VTV+λI)−1VTRT U ^T = \left( V^T V + \lambda I \right)^{-1} V^T R^T
更直观一点，每个用户向量的求解公式如下：
uTi=(VTV+λI)−1VTrTiuiT=(VTV+λI)−1VTriT u_i ^T = \left( V^T V + \lambda I \right)^{-1} V^T r_i^T
uTiuiTu_i^T 为矩阵 UUU 的第 iii 行的转置 (k×1k×1k \times 1)，rTiriTr_i^T 为矩阵 RRR 的第 iii 行的转置 (n×1n×1n \times 1)。
固定 UUU 求解 VVV
VT=(UTU+λI)−1UTRVT=(UTU+λI)−1UTR V ^T = \left( U^T U + \lambda I \right)^{-1} U^T R
更直观一点，每个物品向量的求解公式如下：
vTj=(UTU+λI)−1UTrTjvjT=(UTU+λI)−1UTrjT v_j ^T = \left( U^T U + \lambda I \right)^{-1} U^T r_j^T
vTjvjTv_j^T 为矩阵 VTVTV^T 的第 jjj 列 (k×1k×1k \times 1)，rTjrjTr_j^T 为矩阵 RRR 的第 jjj 列 (m×1m×1m \times 1)。
隐式反馈
固定 VVV 求解 UUU
UT=(VTCvV+λI)−1VTCvRTUT=(VTCvV+λI)−1VTCvRT U ^T = \left( V^T C_v V + \lambda I \right)^{-1} V^T C_v R^T
更直观一点，每个用户向量的求解公式如下：
uTi=(VTCvV+λI)−1VTCvrTiuiT=(VTCvV+λI)−1VTCvriT u_i ^T = \left( V^T C_v V + \lambda I \right)^{-1} V^T C_v r_i^T
uTiuiTu_i^T 为矩阵 UUU 的第 iii 行的转置 (k×1k×1k \times 1)，rTiriTr_i^T 为矩阵 RRR 的第 iii 行的转置 (n×1n×1n \times 1)， CvCvC_v 为对角矩阵 (n×nn×nn \times n)。
固定 UUU 求解 VVV
VT=(UTCuU+λI)−1UTCuRVT=(UTCuU+λI)−1UTCuR V ^T = \left( U^T C_u U + \lambda I \right)^{-1} U^T C_u R
更直观一点，每个物品向量的求解公式如下：
vTj=(UTCuU+λI)−1UTCurTjvjT=(UTCuU+λI)−1UTCurjT v_j ^T = \left( U^T C_u U + \lambda I \right)^{-1} U^T C_u r_j^T
vTjvjTv_j^T 为矩阵 VTVTV^T 的第 jjj 列 (k×1k×1k \times 1)，rTjrjTr_j^T 为矩阵 RRR 的第 jjj 列 (m×1m×1m \times 1),， CuCuC_u 为对角矩阵 (m×mm×mm \times m)。
Spark 分布式实现
上述 ALS 算法虽然明朗了，但是要将其实现起来并不是信手拈来那么简单，尤其是数据量较大，需要使用分布式计算来实现，就更加不是那么地容易了。下面详细阐述 Spark ML 是如何完成 ALS 分布式实现的。为了更加直观的了解其分布式实现，下面用前面的打分矩阵作为例子，如下图所示。
由前面的原理介绍可知，按照显示反馈模型，固定 UUU 求解 VVV，每个物品对隐含特征的偏好向量 vTjvjT v_j ^T 由以下公式得到：
vTj=(UTU+λI)−1UTrTjvjT=(UTU+λI)−1UTrjT v_j ^T = \left( U^T U + \lambda I \right)^{-1} U^T r_j^T
计算时，只需要计算得到 UTU+λIUTU+λI U^T U + \lambda I 和 UTrTjUTrjTU^T r_j^T，再利用 BLAS 库即可解方程，初次迭代计算时，随机初始化矩阵 UUU，假设得到如下初始形式：
U=⎡⎣⎢⎢−u1−−u2−−u3−⎤⎦⎥⎥U=[−u1−−u2−−u3−] U = \begin{bmatrix} -u_1- \ -u_2- \ -u_3- \end{bmatrix}
假如求解 vT1v1Tv_1^T，由于只有 u1u1u_1 和 u2u2u_2 对 v1v1v_1 有打分，那么只需基于 u1u1u_1 和 u2u2u_2 来计算，根据相关线性代数知识就可以得到：
UTU=uT1u1+uT2u2UTrT1=[uT1uT2][45]=4uT1+5uT2UTU=u1Tu1+u2Tu2UTr1T=[u1Tu2T][45]=4u1T+5u2T \begin{split} &U^T U = u_1^T u_1 + u_2^T u_2 \ &U^T r_1^T = {\begin{bmatrix} u_1^T & u_2^T \end{bmatrix}} {\begin{bmatrix} 4 \ 5 \end{bmatrix}} = 4u_1^T + 5u_2^T \end{split}
有了这个基本求解思路后，考虑 uuu 的维度为 kkk，可以在单机上完成上述求解，那么就可以在不同 task 里完成不同物品 vTvTv^T 的计算，实现分布式求解，由打分矩阵可以得到如下图所示的关系图。
基于上述思路，就是要把有打分关联的 u 和 v 想办法放到同一个分区里，这样就可以在一个 task 里完成对 v 的求解，例如要求解 v1v1v_1，就必须把 u1u1u_1 和 u2u2u_2 以及其对应地打分放到同一个分区，才能利用上述公式求解。首先对 uid 和 vid 以 Hash 分区的方式分区，假设分区数均为 2，那么分区后的大致情况如下图所示，v1v1v_1 和 v3v3v_3 在同一个分区中被求解，v2v2v_2 和 v4v4v_4 在同一个分区中被求解。
上面的图仅为感性认识图，实际上手头仅有的数据就是打分矩阵，可以通过一个 RDD 表示打分矩阵ratings，RDD 中的每条记录为(uid, vid, rating)形式，由于是基于 UUU 求解 VVV，把 uid 称之为srcId，vid 称之为dstId，按照srcId和dstId的分区方式，将ratings重新分区，得到的 RDD 为blockRatings，其中的每条记录为((srcBlockId, dstBlockId), RatingBlock)形式，key 为srcId和dstId对应的分区 id 组成的二元组，value(RatingBlock) 包含一个三元组(srcIds, dstIds, ratings)。对于前面的打分关系，原始打分矩阵重新分区如下图所示。
对于 u 来说，是要将自身信息发给不同的 v，对于 v 来说，是要接收来自不同 u 的信息，例如，要将 u1u1u_1 发给 v1v1v_1、v2v2v_2、v3v3v_3 ，v1v1v_1 要接收 u1u1u_1 和 u2u2u_2。那么基于上述重新分区后的打分 RDD，分别得到关于 u 的出口信息userOutBlocks，以及 v 的入口信息itemInBlocks，就可以通过join将两者联系起来计算了。由于后面基于 VVV 求 UUU，也需要求解关于 u 的入口信息userInBlocks，以及 v 的出口信息itemOutBlocks，所以一次性计算好并缓存起来。以计算 u 的入口信息和出口信息为例，在前面得到的重新分区后的blockRatings基础上求解，如下图所示。
首先通过一个map操作，将记录形式((srcBlockId, dstBlockId), RatingBlock)转换为(srcBlockId, (dstBlockId, srcIds, dstLocalIndices, ratings))，其中dstLocalIndices为dstIds去重排序后，每个dstId的索引，最后根据srcBlockId做groupByKey，合并相同srcBlockId对应的 value，合并过程中，对dstLocalIndices中的每个元素加上其对应的dstBlockId，这里做了一个优化，就是将localIndex和blockId用一个Int编码表示，同时采用类似 CSC 压缩编码的方式，进一步压缩srcIds和dstIds的对应关系。这样就按照 uid 进行分区后，得到 u 的入口信息，即将跟 u 关联的 v 绑定在一起了。基于该入口信息，可以进一步得到 u 的出口信息，如下图所示。
在userInBlocks基础上根据srcId和dstId的对应关系，通过map操作将(srcBlockId, (srcIds, dstPtrs, dstEncodedIndices, ratings))形式的记录转换为(srcBlockId, OutBlock)得到userOutBlocks，其中OutBlock是一个二维数组，有numDstBlock行，每一行为srcId所在srcBlockId中的索引，意为当前srcBlockId应该往每个dstBlockId发送哪些用户信息。
同理，在userInBlocks基础上初始化用户信息，得到userFactors，如下图所示，其中 u1u1u_1、u2u2u_2、u3u3u_3 为随机初始化的向量 (1×k1×k1 \times k)。
接着对userOutBlocks和userFactors做join 就可以模拟发送信息了，userOutBlocks中保存了应该往哪里发送的信息，userFactors中保存了用户信息，即一个掌握了方向，一个掌握了信息，如下图所示：
完成了从 u 到 v 的信息发送，后面就是基于 v 的入口信息来收集来自不同 u 的信息了，计算 v 的入口信息跟计算 u 的入口信息一样，只是先要把打分数据blockRatings的 src 和 dst 交换一下，如下图所示。
将itemInBlocks与前面的userOut做join，即可将具有相同dstBlockId的记录拉到一起，userOut中包含来自 u 的信息，itemInBlocks包含了与 src 的对应关系以及打分数据，针对每个 v 找到所有给它发送信息的 u，进而套最小二乘正规方程计算得到itemFactors。
得到itemFactors后可以以同样的方法基于 VVV 求解 UUU，如此交替求解，直到最大迭代次数为止。
总结
ALS 从基本原理上来看应该是很好理解的，但是要通过分布式计算来实现它，相对而言还是较为复杂的，本文重点阐述了 Spark ML 库中 ALS 的实现，要看懂以上计算流程，请务必结合源代码理解，凭空理解上述流程可能比较困难，在实际源码实现中，使用了很多优化技巧，例如使用在分区中的索引代替实际 uid 或 vid，实现Int代替Long，使用数组等连续内存数据结构避免由于过多对象造成 JVM GC 后的内存碎片等。
转载请注明出处，本文永久链接：http://sharkdtu.com/posts/ml-als.html